package com.zhengb.algorithmdemo.leetcode.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 * <p>
 * 例如：
 * 给定二叉树 [3,9,20,null,null,15,7],
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回锯齿形层次遍历如下：
 * <p>
 * [
 * [3],
 * [20,9],
 * [15,7]
 * ]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author zhengbo
 * @date 2020/3/26
 */
public class ZigZagLevelTree {

    public static void main(String[] args) {

        TreeNode three = new TreeNode(3);
        TreeNode nine = new TreeNode(9);
        TreeNode twenty = new TreeNode(20);
        TreeNode seven = new TreeNode(7);
        TreeNode ten = new TreeNode(10);
        TreeNode fifteen = new TreeNode(15);
        TreeNode twenteenOne = new TreeNode(21);

        three.left = nine;
        three.right = twenty;

        nine.left = seven;
        nine.right = ten;

        twenty.left = fifteen;
        twenty.right = twenteenOne;

        ZigZagLevelTree zigZagLevelTree = new ZigZagLevelTree();
        List<List<Integer>> lists = zigZagLevelTree.zigzagLevelOrder(three);

        System.out.println(lists);

    }

    private List<TreeNode> pollAllElements(LinkedList<TreeNode> queue) {

        List<TreeNode> nodeList = new ArrayList<>(queue.size());
        while (!queue.isEmpty()) {
            nodeList.add(queue.poll());
        }
        return nodeList;
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        List<List<Integer>> resultList = new ArrayList<>();

        LinkedList<TreeNode> queue = new LinkedList<>();

        queue.add(root);

        int curLevelIndex = 1;

        while (!queue.isEmpty()) {

            List<TreeNode> nodeList = pollAllElements(queue);

            List<Integer> currentLevelValues = new LinkedList<>();

            for (TreeNode node : nodeList) {

                currentLevelValues.add(node.val);

                if ((curLevelIndex + 1) % 2 != 0) {
                    if (node.right != null) {
                        queue.push(node.right);
                    }
                    if (node.left != null) {
                        queue.push(node.left);
                    }
                } else {
                    if (node.left != null) {
                        queue.push(node.left);
                    }
                    if (node.right != null) {
                        queue.push(node.right);
                    }
                }

            }
            curLevelIndex++;

            resultList.add(currentLevelValues);
        }

        return resultList;

    }
}
